In recent years, discrete wavelet transformation has received a lot of attention in various fields of image processes such as analysis, compression, and recognition of digital signals. Especially, in the image compression field, since a signal entropy reduction effect of the discrete wavelet transformation is high, and a subband decomposition process is suitable for scalable transmission of an image, image compression methods using the discrete wavelet transformation have been extensively examined. It is already determined that a new still image encoding scheme JPEG2000, which will be recommended soon as international standards ITU-T T.800|ISO/IEC 15444, would adopt discrete wavelet transformation.
Conventionally, it is difficult to implement the discrete wavelet transformation of an image due to its memory cost problems, complexity in calculations, and the like. However, simple implementation using a lifting scheme has been examined since I. Daubechies, W. Swelden, et al. have proposed that all discrete wavelet transforms can be decomposed into simple filter lifting steps.
As an example of discrete wavelet transformation, the discrete wavelet transforms of a one-dimensional digital signal sequence x(n) are computed using a 5×3 filter by:
                              r          ⁡                      (            n            )                          =                                            -                              x                ⁡                                  (                                                            2                      ⁢                      n                                        -                    2                                    )                                                      /            8                    +                                    x              ⁡                              (                                                      2                    ⁢                    n                                    -                  1                                )                                      /            4                    +                      3            ×                                          (                                  2                  ⁢                  n                                )                            /              4                                +                                    x              ⁡                              (                                                      2                    ⁢                    n                                    +                  1                                )                                      /            4                    -                                    x              ⁡                              (                                                      2                    ⁢                    n                                    +                  2                                )                                      /            8                                              (        1        )            d(n)=−x(2n)/2+x(2n+1)−x(2n+2)/2  (2)
When this 5×3 filter is formed based on the lifting scheme, equations (1) and (2) are respectively modified as:r(n)=x(2n)+(d(n−1)+d(n))/4  (3)d(n)=x(2n+1)−(x(2n)+x(2n+2))/2  (4)
As can be seen from equations (3) and (4), the number of times of arithmetic operations and the number of times of required data access can be reduced compared to equations (1) and (2).
When a two-dimensional (2D) signal sequence such as an image signal or the like undergoes discrete wavelet transformation, the aforementioned transformation process for the one-dimensional signals is applied in the horizontal and vertical directions. Most of image signals are exchanged in the raster scan order. In such case, image signals or intermediate values of arithmetic operations must be stored for a required number of lines in order to implement transformation in the vertical direction.
FIG. 3 is a block diagram of an apparatus (signal processing apparatus) which implements 2D discrete wavelet transformation using the 5×3 filter by the conventional method. Referring to FIG. 3, reference numeral 300 denotes a signal input unit for inputting image signals; 301, a signal storage processor for controlling storage of the input image signals in a buffer 302 for respective lines; 302, a buffer for storing the image signals for respective lines; 303, a vertical discrete wavelet transformer for computing the discrete wavelet transforms of image signals for a plurality of lines stored in the buffer 302 in the vertical direction; 304, a start address storage unit for storing the start addresses of respective lines stored in the buffer 302; 305, a horizontal discrete wavelet transformer for computing the discrete wavelet transforms of transform coefficients of an L subband obtained by the vertical discrete wavelet transformer in the horizontal direction; and 306, a horizontal discrete wavelet transformer for computing the discrete wavelet transforms of transform coefficients of an H subband obtained by the vertical discrete wavelet transformer in the horizontal direction.
Assume that the signal processing apparatus shown in FIG. 3 computes the transforms of 2D signals which have X samples in the horizontal direction, and Y samples in the horizontal direction, and in which each sample is expressed by 8 bits. The discrete wavelet transformation apparatus in FIG. 3 computes the discrete wavelet transforms of 2D signals for one stage to generate coefficients of four subbands LL, LH, HL, and HH. It is a common practice to further decompose the LL subband into subbands. In such case, a method of preparing a plurality of apparatuses with the arrangement shown in FIG. 3, and operating them in series, or selectively using a single apparatus by switching input data is adopted.
In consideration of a case wherein the apparatuses are connected in series upon operation, Sx represents the number of samples in the horizontal direction of signals input to each apparatus. For example, when two apparatuses operate in series, the number Sx of samples in the horizontal direction of signals input to the first apparatus is X, and the number Sx of samples in the horizontal direction of signals input to the second apparatus is floor{(X+1)/2}. Note that floor{R} is a function of obtaining a maximum integer smaller than real number R. The buffer 302 in FIG. 3 stores signals and intermediate values of arithmetic operations for a plurality of lines, which are required to implement the 5×3 filter. In case of implementation without any lifting, five lines in the vertical direction are required to obtain five signals x(2n−2) to x(2n+2) (five signals in the vertical direction), as can be seen from equations (1) and (2). On the other hand, if the lifting scheme is used, arithmetic operations given by equations (3) and (4) can be expressed, as shown in FIG. 2, and r(n) and d(n) can be obtained if x(2n), x(2n+1), x(2n+2), and d(n−1) in FIG. 2 are available.
Therefore, the buffer must store data for four lines, i.e., signals for three lines (corresponding to x(2n) to x(2n+2)) and an intermediate value for one line (corresponding to d(n−1)). A case will be exemplified wherein lifting is used. Hence, as the buffer 302, the capacity that can store data for four lines, i.e., a memory with a capacity of 4×Sx is prepared. FIG. 11 shows an example of the configuration of the buffer 302.
The start address storage unit 304 stores the start addresses AD[L] (L=0 to 3) of respective lines for the data for four lines, which are stored in the buffer 302. The start addresses of respective lines are replaced as needed during the transformation process. In an initial state, AD[0], AD[1], AD[2], and AD[3] are respectively 0, Sx, 2×Sx, and 3×Sx (see FIG. 11). The operation of the conventional 2D discrete wavelet transformation apparatus will be described below using FIG. 3.
2D signals to be transformed are input from the signal input unit 300 in the raster scan order. Upon computing the discrete wavelet transforms, it is a common practice to extend signals by reflecting them at their two ends in the horizontal and vertical directions. However, in this case, assume that such signal extension processes are executed outside the apparatus and are not taken into consideration, for the sake of simplicity. In this case, wasteful coefficients are output around coefficients of subbands to be generated (two ends in the horizontal and vertical directions), but only effective coefficients are selected.
The signal storage processor 301 stores the signals input from the signal input unit 300 in the raster scan order in the buffer 302 for respective lines. The signal storage processor 301 internally holds an index value L used to acquire the start address of each line upon storing the received line data. FIG. 4 shows the flow of processes of the signal storage processor 301. Referring to FIG. 4, step S401 is the step of initializing index L to 1, step S402 is the step of acquiring the start address AD[L] of line data in the buffer 302, step S403 is the step of storing line data in the buffer 302, step S404 is the step of updating index L, steps S405, S406, S407, and S408 are the steps of instructing the vertical discrete wavelet transformer 303 to compute the discrete wavelet transforms in the vertical direction if index L is 2, or updating index L in other cases, and step S409 is the step of checking if the line of interest is the last line.
At the beginning of the transformation process, index L is initialized to 1 (step S401). The start address AD[L] upon storing line data is acquired from the start address storage unit 304 (step S402). Signals for one line input from the signal input unit 300 are stored in turn from the address AD[L] of the buffer 302 (step S403). Upon completion of storage of signals for one line, index L is incremented by 1 to update the index (step S404). If index L=4, index L is re-set to 2 (steps S405 and S406). It is then checked if index L=2 (step S407). If L=2, the processor 301 instructs the vertical discrete wavelet transformer 303 to compute the discrete wavelet transforms in the vertical direction (step S408). It is then checked if the stored signals for one line correspond to the last line of the two-dimensional signals to be transformed (step S409). If NO in step S409, the process is repeated from step S402; otherwise, the process ends.
After required data are stored in the buffer 302, the vertical discrete wavelet transformer 303 computes the discrete wavelet transforms in the vertical direction to generate coefficients of low- and high-frequency components for one line, and outputs the coefficients of low-frequency components onto a signal line 307, and those of high-frequency components onto a signal line 308. Required data are stored in the buffer 302 at a timing when the index value L of the signal storage processor 301 is set to be 2.
FIG. 5 shows the flow of transformation processes for generating low- and high-frequency components for one line by the vertical discrete wavelet transformer 303. Referring to FIG. 5, step S501 is the step of acquiring start addresses AD[0] to AD[3] of respective lines, step S502 is the step of substituting zero in variable i, step S503 is the step of executing a vertical discrete wavelet transformation process for one set of data to generate a coefficient of one low-frequency component and that of one high-frequency component, step S504 is the step of incrementing variable i by 1, step S505 is the step of comparing variable i with the number Sx of samples in the horizontal direction, and step S506 is the step of updating the start addresses of respective lines. The processing flow of the vertical discrete wavelet transformer 303 will be explained below using FIG. 5.
In step S501, AD[0], AD[1], AD[2], and AD[3] are read out from the start address storage unit 304. In step S502, zero is substituted in variable i. In step S503, the i-th column of sets of data which are continuous in the vertical direction is read out. The i-th column of sets of data which are continuous in the vertical direction is a data sequence read out from four addresses AD[0]+i, AD[1]+i, AD[2]+i, and AD[3]+i, and data read out from these addresses respectively correspond to d(n−1), x(2n), x(2n+1), and x(2n+2) in one-dimensional discrete wavelet transformation formulas given by equations (3) and (4). Furthermore, in step S503, a low-frequency component r[n] and high-frequency component d[n] are calculated based on equations (3) and (4), a coefficient r[n] of the low-frequency component is output onto the signal line 307, and a coefficient d[n] of the high-frequency component is output onto a signal line 308. At this time, the obtained high-frequency component d[n] is stored at the address where x(2n+1) is stored (i.e., AD[2]+i).
In step S504, i is updated by adding 1 to it. In step S505, i and Sx are compared. If i<Sx, the flow returns to step S503. Upon completion of the vertical discrete wavelet transformation processes in step S503 from i=0 to Sx−1, values stored in AD[0] and AD[1] are exchanged, and values stored in AD[2] and AD[3] are exchanged, and those values are stored in the start address storage unit 304 in step S506.
The horizontal discrete wavelet transformers 305 and 306 execute transformation processes based on equations (3) and (4) for data for one line (coefficients of low- or high-frequency component) respectively input from the signal lines 307 and 308, and generate and output coefficients of low- and high-frequency components.
The aforementioned processes are repeated for all lines input from the signal input unit 300, thus computing the 2D discrete wavelet transforms.
As described above, when 2D signals such as image data or the like are decomposed into subbands, a plurality of data which are continuous in the vertical direction are read out and processed in the vertical transformation. However, when the number of pixels in the horizontal direction of an image such as high-resolution image data or the like is extremely large, data which are continuous in the vertical direction are stored in a memory at discrete positions. For example, when a computer system, which comprises a cache memory that can read/write data at high speed between a central processing unit and main memory, implements discrete wavelet transformation of image data by software, the cache hit rate is high and the time required to read out data can be short since data are continuously read out from the memory upon horizontal transformation. However, upon reading out data required for vertical transformation, the hit rate of the cache memory lowers, resulting in a long conversion process.
The present invention has been made in consideration of the aforementioned problems, and has as its object to implement high-speed wavelet transformation process by reducing the time required to read out data to be accessed in wavelet transformation.